package com.sicheng.algorithm.node;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/18 16:46
 */
public class MergeOrderlyList {
    /**
     * Merge
     */

    public static void main(String[] args) {
        ListNode head1 = ListNode.initList(new int[]{1, 3, 5});
        ListNode head2 = ListNode.initList(new int[]{2, 4, 6});

        ListNode head = mergeOrderlyList(head1, head2);
        ListNode.list(head);
    }

    public static ListNode mergeOrderlyList(ListNode head1, ListNode head2) {

        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;

        ListNode temp;
        if (head1.val > head2.val) {
            temp = head2;
            head2 = head1;
            head1 = temp;
        }
        temp = head1;
        while (head1.next != null) {
            if ((head2.val == head1.val ||
                    (head2.val > head1.val && head2.val < head1.next.val))) {
                ListNode head2_next = head2.next;
                head2.next = head1.next;
                head1.next = head2;
                head2 = head2_next;
                if (head2_next == null)
                    break;
            }
            head1 = head1.next;

        }

        if (head1.next == null)
            head1.next = head2;


        return temp;
    }
}
